/**
//三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模100
//0000007。 
//
// 示例1: 
//
// 
// 输入：n = 3 
// 输出：4
// 说明: 有四种走法
// 
//
// 示例2: 
//
// 
// 输入：n = 5
// 输出：13
// 
//
// 提示: 
//
// 
// n范围在[1, 1000000]之间 
// 
// Related Topics 记忆化搜索 数学 动态规划 👍 65 👎 0

*/

package com.xixi.easy;
public class ID_mian_08_01_ThreeStepsProblemLcci {
public static void main(String[] args) {
Solution solution = new ID_mian_08_01_ThreeStepsProblemLcci().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    int[] resultArr = new int[1000001];
    public int waysToStep(int n) {

        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n <= 0 ) return 1;

        if(resultArr[n] != 0){
            return resultArr[n];
        }else {
            //三级楼梯以上，前面的楼梯可能是一步迈上来， 也可能是两步迈上来，也可能是三步迈上来
            resultArr[n] = ((waysToStep(n-1) + waysToStep(n-2)) % 1000000007+ waysToStep(n -3)% 1000000007) % 1000000007;
            return resultArr[n];
        }

    }
}
//leetcode submit region end(Prohibit modification and deletion)




}